﻿//使⽤最⼩花费爬楼梯（easy）：https://leetcode.cn/problems/min-cost-climbing-stairs/
//v1:
class Solution
{
public:
 int minCostClimbingStairs(vector<int>& cost)
 {
 int n = cost.size();
 // 初始化⼀个 dp表
 vector<int> dp(n + 1, 0);
 // 初始化
 dp[0] = dp[1] = 0;
 // 填表
 for (int i = 2; i < n + 1; i++)
 // 根据状态转移⽅程得
 dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
 // 返回结果
 return dp[n];
 }
}；

//v2:
class Solution
{
public:
 int minCostClimbingStairs(vector<int>& cost) 
 {
 // 1. 创建 dp 表
 // 2. 初始化
 // 3. 填表顺序
 // 4. 返回值
 int n = cost.size();
 vector<int> dp(n);
 dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
 for(int i = n - 3; i >= 0; i--)
 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];
 return min(dp[0], dp[1]);
 }
};

//解码⽅法（medium）: https://leetcode.cn/problems/decode-ways/
class Solution
{
public:
 int numDecodings(string s) 
 {
 int n = s.size();
 vector<int> dp(n); // 创建⼀个 dp表
 // 初始化前两个位置
 dp[0] = s[0] != '0';
 if(n == 1) return dp[0]; // 处理边界情况
 if(s[1] <= '9' && s[1] >= '1') dp[1] += dp[0];
 int t = (s[0] - '0') * 10 + s[1] - '0';
 if(t >= 10 && t <= 26) dp[1] += 1;
 // 填表
 for(int i = 2; i < n; i++)
 {
 // 如果单独编码
 if(s[i] <= '9' && s[i] >= '1') dp[i] += dp[i - 1];
 // 如果和前⾯的⼀个数联合起来编码
 int t = (s[i - 1] - '0') * 10 + s[i] - '0';
 if(t >= 10 && t <= 26) dp[i] += dp[i - 2];
 }
 // 返回结果
 return dp[n - 1];
 }
};